import java.util.ArrayList;
import java.util.HashSet;

import edu.princeton.cs.algs4.Digraph;
import edu.princeton.cs.algs4.In;
import edu.princeton.cs.algs4.LinearProbingHashST;
import edu.princeton.cs.algs4.Queue;
import edu.princeton.cs.algs4.SequentialSearchST;
import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.Stack;

//最短祖先路径。有向图中 两个顶点 v和w之间的祖先路径 是从v到共同祖先x 的有向路径，以及从w到同一祖先x 的有向路径。
//找最短祖先路径，就和找最小公倍数差不多，两个点都往上找，找到他们能交汇的那个点就是了，当然还要满足是最小的。
//最短祖先路径是总长度最小的祖先路径。我们将最短祖先路径中的共同祖先称为 最短共同祖先
public class SAP {
  private Digraph g;

  // constructor takes a digraph (not necessarily a DAG)
  public SAP(Digraph G) {
    g = new Digraph(G);
  }

  private class BFS_all {
    int distance;
    int ancestor;
    String edge;
  }

  private BFS_all BFS(Digraph g, int a, int b) {
    // ArrayList<Integer> marked = new ArrayList<Integer>(); 用于判断每步结束是否出现重复元素
    // 出现错误，没考虑到同一边的广度优先访问到同一个点
    HashSet<Integer> markedA = new HashSet<Integer>();
    HashSet<Integer> markedB = new HashSet<Integer>();
    LinearProbingHashST<Integer, Integer> distanceTo_A = new LinearProbingHashST<Integer, Integer>(); // 用于判断走了多远
    LinearProbingHashST<Integer, Integer> distanceTo_B = new LinearProbingHashST<Integer, Integer>();
    SequentialSearchST<Integer, Integer> edgeTo_A = new SequentialSearchST<Integer, Integer>(); // 用于返回路径
    SequentialSearchST<Integer, Integer> edgeTo_B = new SequentialSearchST<Integer, Integer>(); // 用于返回路径
    Queue<Integer> points_A = new Queue<Integer>();
    Queue<Integer> points_B = new Queue<Integer>();
    int ancestor_Id = -1; // 祖先的id
    points_A.enqueue(a);
    points_B.enqueue(b);
    markedA.add(a);
    markedB.add(b);
    if (markedB.contains(a) && ancestor_Id == -1) // 这里是找到了
    {
      ancestor_Id = a;
    }
    distanceTo_A.put(a, 0);
    distanceTo_B.put(b, 0);
    int A_loop = 0;
    int B_loop = 0;
    int i = 0;// 用i标注目前进行到第几步了
    // 这里开始是总循环，结束条件是到最后也没找到最短祖先（条件是两个队列都空了）或者找到了最短祖先。
    while (!(points_A.isEmpty() && points_B.isEmpty())
        && (ancestor_Id == -1 || i + 1 < distanceTo_A.get(ancestor_Id) + distanceTo_B.get(ancestor_Id))) {
      i++;
      // A走一步
      if (!points_A.isEmpty()) {
        for (A_loop = points_A.peek();; A_loop = points_A.peek()) {
          if (distanceTo_A.get(A_loop) >= i) {
            break;
          } else {
            A_loop = points_A.dequeue();
          }
          for (int point : g.adj(A_loop)) {
            if (!markedA.contains(point)) {
              points_A.enqueue(point);
              edgeTo_A.put(point, A_loop);// point从A_loop那里来
              distanceTo_A.put(point, distanceTo_A.get(A_loop) + 1);// pdistanceTo_A.get(ancestor_Id) +
                                                                    // distanceTo_B.get(ancestor_Id)oint的距离是A_loop+1
              markedA.add(point); // 添加以之后判断是否有重复元素
              if (markedB.contains(point) && (ancestor_Id == -1 || distanceTo_A.get(ancestor_Id)
                  + distanceTo_B.get(ancestor_Id) > distanceTo_A.get(point) + distanceTo_B.get(point))) // 这里是找到了
              {
                ancestor_Id = point;
              }
            }

          }
          if (points_A.isEmpty()) {
            break;
          }
        }
      }
      // B走一步
      if (!points_B.isEmpty()) {
        for (B_loop = points_B.peek();; B_loop = points_B.peek()) {
          if (distanceTo_B.get(B_loop) >= i) {
            break;
          } else {
            B_loop = points_B.dequeue();
          }
          for (int point : g.adj(B_loop)) {
            if (!markedB.contains(point)) {
              points_B.enqueue(point);
              edgeTo_B.put(point, B_loop);
              distanceTo_B.put(point, distanceTo_B.get(B_loop) + 1);
              markedB.add(point);
              if (markedA.contains(point) && (ancestor_Id == -1 || distanceTo_A.get(ancestor_Id)
                  + distanceTo_B.get(ancestor_Id) > distanceTo_A.get(point) + distanceTo_B.get(point))) {
                ancestor_Id = point;
              }
            }
          }
          if (points_B.isEmpty()) {
            break;
          }
        }
      }
    }
    BFS_all val = new BFS_all();
    val.ancestor = ancestor_Id;
    if (ancestor_Id == -1) // 没找到
    {
      val.distance = -1;
      val.edge = "-1";
      return val;
    }
    val.distance = distanceTo_A.get(ancestor_Id) + distanceTo_B.get(ancestor_Id);
    String edge = new String();
    // 这里是从A到ancestor
    Stack<Integer> path = new Stack<Integer>();
    for (int point = ancestor_Id; point != a; point = edgeTo_A.get(point)) {
      if (point == ancestor_Id) {
        continue;
      }
      path.push(point);
    }
    path.push(a);
    for (Integer point : path) {
      edge = edge + point + " ";
    }
    // 这里是从ancestor到B
    ArrayList<Integer> path_b = new ArrayList<Integer>();
    for (int point = ancestor_Id, k = 0; point != b; point = edgeTo_B.get(point), k++) {
      path_b.add(k, point);
    }
    path_b.add(b);
    for (Integer point : path_b) {
      edge = edge + point + " ";
    }
    val.edge = edge;
    return val;
  }

  // length of shortest ancestral path between v and w; -1 if no such path
  public int length(int v, int w) {
    if (v == w) {
      return 0;
    }
    return BFS(g, v, w).distance;
  }

  // a common ancestor of v and w that participates in a shortest ancestral path;
  // -1 if no such path
  public int ancestor(int v, int w) {
    return BFS(g, v, w).ancestor;
  }

  // length of shortest ancestral path between any vertex in v and any vertex in
  // w; -1 if no such path
  // v 中任何顶点和 w 中任何顶点之间的最短祖先路径的长度；如果没有这样的路径，则 -1
  public int length(Iterable<Integer> v, Iterable<Integer> w) {
    int length = -1;
    int lengthMin = -1;
    for (Integer point_v : v) {
      for (Integer point_w : w) {
        length = BFS(g, point_v, point_w).distance;
        if (lengthMin==-1|| lengthMin> length) {
          lengthMin = length;
        }
      }
    }
    return lengthMin;
  }

  // a common ancestor that participates in shortest ancestral path; -1 if no such
  // path
  // 参与最短祖先路径的共同祖先；如果没有这样的路径，则 -1
  public int ancestor(Iterable<Integer> v, Iterable<Integer> w) {
    BFS_all BFS_tmp = new BFS_all();
    BFS_all BFSMin = new BFS_all();
    BFSMin.ancestor = -1;
    BFSMin.distance = -1;
    for (Integer point_v : v) {
      for (Integer point_w : w) {
        BFS_tmp = BFS(g, point_v, point_w);
        if (BFSMin.distance > BFS_tmp.distance || BFSMin.ancestor == -1) {
          BFSMin = BFS_tmp;
        }
      }
    }
    return BFSMin.ancestor;
  }

  // do unit testing of this class
  public static void main(String[] args) {
    In in = new In("digraph3.txt");
    Digraph G = new Digraph(in);
    SAP sap = new SAP(G);
    while (!StdIn.isEmpty()) {
      int v = StdIn.readInt();
      int w = StdIn.readInt();
      int length = sap.length(v, w);
      int ancestor = sap.ancestor(v, w);
      StdOut.printf("length = %d, ancestor = %d\n", length, ancestor);
    }
  }
}
